package com.zwj.interview.动态规划;

/**
 * 题目：一个数组cost的所有数字都是正数，它的第i个数字表示在一个楼梯的第i级台阶往上爬的成本，
 * 在支付了成本cost[i]之后可以从第i级台阶往上爬1级或2级。假设台阶至少有2级，既可以从第0级台阶出发，
 * 也可以从第1级台阶出发，请计算爬上该楼梯的最少成本。例如，输入数组[1，100，1，1，100，1]，
 * 则爬上该楼梯的最少成本是4，分别经过下标为0、2、3、5的这4级台阶，如图14.1所示。
 */
public class 爬楼梯 {

    //dp[i]表示到达下标i的位置的最小成本
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        //由于可以选择下标 0 或 1 作为初始阶梯，所以有dp[0]=dp[1]=0
        dp[0] = dp[1] = 0;
        //当i在[2，n]时，那么对于下标为i的楼梯，可以选择从i-1位置，走一步，成本是:dp[i - 1] + cost[i - 1]
        //也可以从i-2位置，走两步 ,成本是：dp[i - 2] + cost[i - 2]
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }


    //我们使用dp[i]表示到达下标为i的位置的最小成本
    public int minCostClimbingStairs2(int[] cost) {
        int n=cost.length;
        int[] dp=new int[n+1];
        //由于可以从下标0或者1的位置出发，所以，dp[0]、dp[1]
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<=n;i++){
          dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];

    }


}
